package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <p>
 *          <a href="https://leetcode.cn/problems/remove-nodes-from-linked-list/description/">从链表中移除节点</a><br/>
 *          给你一个链表的头节点 head 。移除每个右侧有一个更大数值的节点。返回修改后链表的头节点 head 。<br/>
 *          例：<br/>
 *          输入：head = [5,2,13,3,8]<br/>
 *          输出：[13,8]<br/>
 *          解释：需要移除的节点是 5 ，2 和 3 。  <br/>
 *                  - 节点 13 在节点 5 右侧。   <br/>
 *                  - 节点 13 在节点 2 右侧。   <br/>
 *                  - 节点 8 在节点 3 右侧。    <br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/3 13:34
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode2487 {

    /**
     * <p>
     *     给你一个链表的头节点 head,移除每个右侧有一个更大数值的节点,返回修改后链表的头节点 head。[使用递归]
     * </p>
     * @param head 链表的头节点 head
     * @return 修改后链表的头节点 head
     */
    public static ListNode removeNodes(ListNode head) {
        // 链表为空
        if (head == null) return null;
        // 递归调用 先将链表全递归一次
        head.next = removeNodes(head.next);
        // 停止递归条件 最后一个节点不为空,且当前节点的值 < 下一个节点的值。 或者 当前节点值 >= 下一个节点值
        if (head.next != null && head.val < head.next.val) {
            return head.next;
        } else return head;
    }

    /**
     * <p>
     *     给你一个链表的头节点 head,移除每个右侧有一个更大数值的节点,返回修改后链表的头节点 head。[使用单调栈]
     * </p>
     * @param head 链表的头节点 head
     * @return 修改后链表的头节点 head
     */
    public static ListNode checkRemoveNodes(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        // 将链表压入栈中,head指向空节点
        for (; head != null ; head = head.next) {
            stack.push(head);
        }

        // 遍历栈, 第一次遍历时 head指向Null
        // 栈结构 先进后出,即 弹出节点 >= head。val,则将当前节点加入到链表
        for (; !stack.isEmpty(); stack.pop()) {
            if (head == null || stack.peek().val >= head.val) {
                // 如果当前弹出元素的值 >= head的值,将当前弹出节点的next指针指向head链表
                stack.peek().next = head;
                // 将head指针指向当前弹出元素
                head = stack.peek();
            }
        }
        return head;
    }

    public static void main(String[] args) {
        int maxLen = 5;
        int maxVal = 50;
        int testTimes = 10000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            ListNode head = ListNode.generateListNode(maxLen, maxVal);
            if (ListNode.getNodeLength(removeNodes(head)) != ListNode.getNodeLength(checkRemoveNodes(head))) {
                System.out.println("Oops");
                ListNode.printNode(head);
            }
        }
        System.out.println("Test Finish!");
    }
}
